package sort;
/*
* Offer03. 数组中的重复数字
*
*   原地交换可以节省空间, 不用创建set或者数组了
* */
public class Offer03findRepeatNumber {
    public int findRepeatNumber(int[] nums) {
//        int n=nums.length;
//        int[] tmp=new int[n];
//        int res=-1;
//        for(int i=0;i<n;i++){
//            if(tmp[nums[i]]!=0){
//                res=nums[i];
//            }
//            tmp[nums[i]]++;
//        }
//        return res;
        int n=nums.length;
        int i=0;
        while(i<n){
            if(nums[i]==i){
                i++;
                continue;
            }
            if(nums[i]==nums[nums[i]])return nums[i];
            int tmp=nums[nums[i]];
            nums[nums[i]]=nums[i];
            nums[i]=tmp;
        }
        return -1;
    }
}
